package simple.string;

/**
 * @Desc <a href="https://leetcode.cn/problems/backspace-string-compare/">844. 比较含退格的字符串</a>
 * 给定 s 和 t 两个字符串，当它们分别被输入到空白的文本编辑器后，如果两者相等，返回 true 。# 代表退格字符。
 * 注意：如果对空文本输入退格字符，文本继续为空。
 * 示例 1：
 *   输入：s = "ab#c", t = "ad#c"
 *   输出：true
 *   解释：s 和 t 都会变成 "ac"。
 * 示例 2：
 *   输入：s = "ab##", t = "c#d#"
 *   输出：true
 *   解释：s 和 t 都会变成 ""。
 * 示例 3：
 *   输入：s = "a#c", t = "b"
 *   输出：false
 *   解释：s 会变成 "c"，但 t 仍然是 "b"。
 * 提示：
 *   1 <= s.length, t.length <= 200
 *   s 和 t 只含有小写字母以及字符 '#'
 * @Date 2023/6/28 20:32
 * @Created by 刘学松
 */
public class 比较含退格的字符串 {
    public static void main(String[] args) {
        backspaceCompare("nzp#o#g", "b#nzp#o#g");
    }
    public static boolean backspaceCompare(String s, String t) {
        int index1 = s.length()-1, index2 = t.length()-1;
        // 从尾部开始遍历
        while (index1 >= 0 || index2 >= 0) {
            // 需退格次数
            int count1 = 0, count2 = 0;
            // 当前下标的字符，遍历到头了则置为0
            char c1 = index1 >= 0 ? s.charAt(index1) : 0, c2 = index2 >= 0 ? t.charAt(index2) : 0;
            // 对s进行退格，只要是退到#或者需退格次数大于0，则不断退格
            while (c1 == '#' || count1 != 0) {
                // 遇到#，需退格次数+1，否则，需退格次数-1
                if (c1 == '#') {
                    ++count1;
                } else {
                    --count1;
                }
                // 下标前移，移到头了则置为0
                --index1;
                if (index1 < 0) {
                    c1 = 0;
                    break;
                }
                c1 = s.charAt(index1);
            }
            // 对t进行退格，原理同上
            while (c2 == '#' || count2 != 0) {
                if (c2 == '#') {
                    ++count2;
                } else {
                    --count2;
                }
                --index2;
                if (index2 < 0) {
                    c2 = 0;
                    break;
                }
                c2 = t.charAt(index2);
            }
            // s和t都退格到非#字符时，判断二者是否相等，不相等直接返回false
            if (c1 != c2) {
                return false;
            }
            // 二者下标继续前移
            --index1;
            --index2;
        }
        return true;
    }
}
